Internet Protocol (IP) classification is performed in routers. This is the process of classifying IP packets into categories that require special treatment. A subset of IP classification is IP filtering. IP filtering is a security feature that restricts IP traffic by permitting or denying packets by applying certain rules. This way, users can be restricted to specific domains or applications on the Internet. To perform classification, IP headers of packets that reach a router need to be compared to patterns stored in a table, generating an output that classifies the packet. Usually, this table is stored in memory and matching is done in software.
The functionality of filtering and classifying packets treated here is called Multi-field (MF) classification, since it acts on several independent fields in the packet headers, and is used both for Differentiated Services (DiffServ) policy enforcement and security (firewall) filtering.
The IP header fields on which packets can be classified by the filters are:                IP Source Address;        IP destination Address;        IP version—IPv4 or IPv6 or both;        Protocol—next header protocol (layer 4);        DSCP—DS code point (former TOS field);        Source Port—with limited range possibility;        ICMP Type;        TCP Session Established.        
The command based router classifiers is structured in a tree-like hierarchy with a policy map consisting of class maps, access control lists and filters with their match outcomes, actions and match patterns.
Said structures are built in a hierarchy of the components Filters, ACLs (access control lists, or just access lists), CMAPs (class maps) and PMAPs (policy maps). These components will now be described one by one in more detail with reference to FIG. 1:
Filter—this component cannot be specified alone, but only as part of an including ACL. Each filter consists of a match field and a result. The match field is a bit-pattern, wherein “don't care” is allowed, to test for match against defined header fields of packets to be classified. The result is an indication of whether or not a packet matching the match field is considered to belong to the ACL as a whole. Conventionally the result is called either “permit”, meaning “belongs to ACL”, or “deny”, meaning “does not belong to ACL”. (These conventional terms come from the original restricted use of ACLs, which was only to determine access through a firewall.) For the extended use of ACLs employed now, it is suggested using “+” and “−” instead of permit and deny.
ACL—Access Control List, or just access list, is an ordered list of Filters to be tried for match against packets to be classified, starting at the head of the list, and progressing through until some filter matches, or until the end of the list is reached. If the end of the list is reached without any filter matching, it is deemed that the packet does not match the ACL, which could be considered as an implicit filter at the tail of the ACL having bits “don't care” in the match field and “deny” as the result. Each ACL is defined by a management operation and is given a name to use as reference. Filters can be added and removed from existing ACLs. Note that the order of the filters in an ACL is significant, so the position, priority, of added filters can be specified. ACLs can be used in two ways: as a member of a CMAP (see below) or tied directly to an interface as a firewall filter.
CMAP—Class Map is a set (order not significant) of specified (by name, e.g. reference number) ACLs and match operator, also denoted match mode, which is either match-any or match-all. A packet being classified is considered to belong to a class defined by a CMAP either if it matches any of the ACLs in a CMAP having the match-any attribute or, if, and only if, it matches all the ACLs in a CMAP having the match-all attribute. CMAPs are defined by management operations and given a reference name. Existing CMAPs can also be modified. The only use of a CMAP is by membership in a PMAP.
PMAP—Policy Map is an ordered set of CMAPs to which each CMAP is associated with an action. A PMAP can be tied to an interface, and then all packets passing the interface will be tested against the PMAP, starting with the first CMAP and continuing until the packet is found to belong to a CMAP or until all CMAPs have been exhausted. When the packet is found to belong to a CMAP, the associated action is performed. The possible actions are:                FORWARD—which means “forward the packet”;        DROP—drop the packet;        REMARK DSCP n—rewrite the DSCP (DS code point) field of the packet to a specified new value.        
The default action is FORWARD.
Note: When a packet matches a filter having result permit, thus causing the packet to belong to the class defined by a CMAP including this ACL, and in which the CMAP is included in a PMAP with action DROP. The packet is thus dropped due to matching a filter with permit.
Each interface can be tied to at most one PMAP and one firewall ACL (otherwise would not make sense). Inbound and outbound interfaces are treated separately.
Since ACLs are referred to by name, the same ACL can be used in several roles (as member of multiple CMAPs and/or as firewall ACL for various interfaces). Likewise, the same CMAP can be used in multiple PMAPs, and the same PMAP can be tied to various interfaces.
If an interface is tied both to a firewall ACL and to a PMAP, the firewall ACL (ACLFW) is traversed first, and only if a packet is permitted for access is it tested against the PMAP. Interfaces which is not connected to a firewall ACL are implicitly permitted for access.
Due to increasing performance requirements and larger and wider search sets, software-based search algorithms become too slow and alternative implementations need to be considered. One such alternative is to use a Content Addressable Memory (CAM).
A Content Addressable Memory, CAM, is a memory device that has become increasingly valuable during the recent years in some applications. A CAM can perform fast storing and search operations. The CAM provides a performance advantage over memory search algorithms such as binary and tree based searches or look-aside tag buffers by comparing the desired information against the entire list of pre-stored data simultaneously often resulting in an order-of-magnitude reduction of search time. Once information is stored in a CAM location, it is found by comparing every bit in the CAM with the bits of the data in a search expression. If there is a match for every bit in a location with every corresponding bit in the search expression, an output is obtained from the CAM, which is an association value or address pointing to associated information. The associated information may be stored in a conventional memory device such as a RAM. Depending on the application, the RAM can contain information or instructions or operations or the like to be displayed or performed when there is a match between the search expression and the information stored in the CAM. Thus, with a CAM, the data is supplied and the address is obtained.
Because the CAM doesn't need address lines to find data, the depth of a memory system using CAMs can be extended as far as desired, but the width is limited by the size of the chip. For example, a chip can be 64 to 128 bits wide, but 32768 entries deep. It is fairly easy to extend the depth of the CAM, because the addressing is all self-contained.
Some CAMs are so called ternary CAMs in which the stored data can contain bit values of 0, 1 or X, where X is interpreted as “don't care”, i.e. the value matches both 0 and 1.
The function and advantages of the CAM memory makes it very suitable for applications and operations such as LANs, data base management, file storage management, look-up to pattern recognition, and the like, and is particularly suited to performing search operations. To classify a packet, the look-up performance will depend on the search algorithm, and the look-up time is not deterministic using software solutions. Hardware accelerated solutions, such as Ternary Content Addressable Memory (TCAM), will increase the search performance by orders-of-magnitude as the look-up in TCAM entries can be performed with a single operation, typically at one clock cycle. In recent years, TCAMs are becoming faster, bigger and cheaper, and they provide an excellent solution for doing very fast look-ups with deterministic look-up time.
A method in which CAMs of less width are used to store “expressions” in CAMs and to match expressions with the contents of CAMs, where the width of the expressions is larger than the width of the CAMs used, is earlier known from the international patent application WO 02/082458.
From the U.S. Pat. No. 6,484,170 techniques for generating searchable data entries in a CAM, such as binary or ternary CAMs, are earlier known. In said document, a method of classifying data networking packets and a packet classifier based on subfields of a packet header are also described.
Packet classification by using TCAMs is earlier known and treated in a document “Efficient Mapping of Range Classifier into Ternary-CAM” by Huan Liu, published on the internet by Department of Electrical Engineering, Stanford University, CA 94305.
In practice, complications arise because the desired classification rules to be enforced on the traffic flow, as defined by a network manager, consist of a tree-like structure in which it is required to look for more than one possible match against each packet in the flow. Such a structure is straightforward and easy to follow manually, or by a procedural program, but not by a linear CAM array which terminates search at the first matching entry. However, CAMs, such as TCAMs, can only store flat structures and a tree-like hierarchy cannot be stored in it directly. To get a table of CAM entries to provide a behaviour corresponding to that of the tree-like structure, the filter rules must be “flattened” to a linear array, taking advantage of the CAM's ternary capability (“don't care” match at required bit positions). The implementation of the “flattening” of the filter tree is called the “Filter Compiler”. Therefore, an algorithm is needed for compiling the command based router classifiers with a tree-like hierarchy to an equivalent flat CAM friendly structure.